package com.cwj.algorithm.sort;

import java.util.List;

/**
 * @author chenwujie
 * @date 2020/11/1014:02
 */
public class QuickSort {
    public static <T extends Comparable<? super T>> void sort(T[] data) {
        sort(data, 0, data.length);
    }

    public static <T extends Comparable<? super T>> void sort(T[] data, int i, int j) {
        if(i >= j){
            return;
        }
        int partition = partition(data, i, j);
        sort(data, i, partition);
        sort(data, partition + 1, j);
    }

    public static <T extends Comparable<? super T>> int partition(T[] data, int i, int j) {
        T key = data[i];
        int left  = i;
        int right = j;

        while(true){
            while (greater(data[--right], key)){
                if(left == right){
                    break;
                }
            }
            while (greater(key, data[++left])){
                if(left == right){
                    break;
                }
            }
            if(left >= right){
                break;
            }else{
                exchange(data, left, right);
            }
        }
        exchange(data, i, right);

        return right;
    }

    private static <T extends Comparable<? super T>> boolean greater(T a, T b) {
        return a.compareTo(b) > 0;
    }

    private static <T extends Comparable<? super T>> void exchange(List<T> data, int i, int j) {
        T temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    private static <T extends Comparable<? super T>> void exchange(T[] data, int i, int j) {
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
